package two.chapter_2.c2_1;

import edu.princeton.cs.algs4.StdOut;
import two.chapter_1.c1_1.Printer;
import two.chapter_1.c1_3.*;

public class Ex2_1_14 {

    /**
     * 出列排序。将一副扑克牌排序，限制条件是只能查看最上面的两张牌，交换最上面的两张票，或是将最上面的一张牌放到
     * 这摞牌的最下面
     * 每轮从1到N-1，将最上面两张票中较小的一张牌放到这摞牌的最下面，这样一轮下来，整副牌中最大的牌就是第一张，在本轮结束将这张最大的牌放到整副牌的最下面
     * <p>
     * 类似冒泡排序，大的牌一个一个出现在下面。
     * <p>
     * 假设牌为 "6","3","7","9","4","5"
     * 第一轮
     *      679453
     *      794536
     *      945367
     *      953674
     *      936745
     * 第一轮结束  367459   最大值出现在最下面
     *
     * 第二轮
     *      674593
     *      745936
     *      759364
     *      793645
     *      936457
     * 第二轮结束  364579   大的值一个一个下沉
     *
     * ...
     * @param args
     */
    public static void main(String[] args) {
        String[] cards = {"6", "3", "7", "9", "4", "5"};
        DequeueSort<String> sort = new DequeueSort();

        sort.sort(cards);
        Printer.printArray(cards);
    }


    private static class DequeueSort<Item extends Comparable<Item>> extends Sortable<Item> {

        @Override
        public void sort(Item[] items) {
            int N = items.length;
            while (!isSorted(items)) {
                for (int j = 0; j < N - 1; j++) {
                    if (less(items[1], items[0])) {
                        exch(0, 1, items);   //第一张和第二张交换
                    }
                    for (int z = 0; z < N - 1; z++) {

                        exch(z, z + 1, items); //第一张放到最后
                    }
                    Printer.printArray(items);
                }

                for (int z = 0; z < N - 1; z++){
                    exch(z, z + 1, items);//将最大的牌放到最后一张
                }
            }
        }
    }


}
